package com.fanshuai.heap;

/**
 * 极小堆
 * @param <E>
 */
public class MinHeap<E extends Comparable<E>> implements Heap<E> {

    private E[] array;
    private int index;

    public MinHeap(int maxSize) {
        array = (E[]) new Object[maxSize + 1];
        index = 1;
    }

    private void swap(int i, int j) {
        E data = array[i];
        array[i] = array[j];
        array[j] = data;
    }

    private void swim() {
        int curIndex = index - 1;
        while (curIndex > 1) {
            if (array[curIndex].compareTo(array[curIndex / 2]) < 0) {
                swap(curIndex, curIndex / 2);
                curIndex = curIndex / 2;
            } else {
                break;
            }
        }
    }

    private void sink() {
        int curIndex = 1;
        while (2 * curIndex <= index - 1) {
            int j = curIndex * 2;
            if (j < index - 1 && array[j + 1].compareTo(array[j]) < 0) {
                j = j + 1;
            }

            if (array[j].compareTo(array[curIndex]) < 0) {
                swap(j, curIndex);
                curIndex = j;
            } else {
                break;
            }
        }
    }

    @Override
    public void add(E data) throws IndexOutOfBoundsException {
        if (index >= array.length) {
            throw new IndexOutOfBoundsException("out of bounds, index=" + index);
        }

        array[index] = data;
        index++;
        swim();
    }

    @Override
    public E pop() {
        if (index <= 1) {
            return null;
        }

        E data = array[1];
        array[1] = array[index - 1];
        array[index - 1] = null;
        index--;
        sink();

        return data;
    }

    @Override
    public E peek() {
        return array[1];
    }

    @Override
    public int size() {
        return index - 1;
    }

    @Override
    public boolean isEmpty() {
        return index == 1;
    }

    @Override
    public boolean isFull() {
        return index == array.length;
    }
}
